package cn.chen.tree;

import java.util.Vector;

public class BS {

    public int bs(Integer key,int low,int high){
        if(low > high) return low;
        int mid = low + (high - low) / 2;
        int cmp = key.compareTo(mid);
        if(cmp > 0) return bs(key, mid + 1,high);
        else if (cmp < 0) return bs(key, low,mid - 1);
        else return mid;
    }

    public int bs2(Integer key,int low,int high){
        int lo = low;
        int hi = high;
        while(low <= high){
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(mid);
            if (cmp > 0) lo = mid + 1;
            else if(cmp < 0) hi = mid - 1;
            else return mid;
        }
        return lo;
    }

    public int bs3(Integer key,int[] arr){
        int lo = 0;
        int hi = arr.length;
        while(lo <= hi){
            // 下标
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(arr[mid]);
            if(cmp > 0) lo = mid + 1;
            else if(cmp < 0) hi = mid - 1;
            else return mid;
        }
        return lo;
    }

}
